package com.lfg.leetcode.leetcode100;


import java.util.*;

public class No126findLadders {

    public static void main(String[] args) {
        List<String> list = new ArrayList<>(Arrays.asList("hot,dog".split(",")));
//        List<String> list = new ArrayList<>(Arrays.asList("hot,dot,dog,lot,log,cog".split(",")));
//        List<String> list = new ArrayList<>(Arrays.asList("si,go,se,cm,so,ph,mt,db,mb,sb,kr,ln,tm,le,av,sm,ar,ci,ca,br,ti,ba,to,ra,fa,yo,ow,sn,ya,cr,po,fe,ho,ma,re,or,rn,au,ur,rh,sr,tc,lt,lo,as,fr,nb,yb,if,pb,ge,th,pm,rb,sh,co,ga,li,ha,hz,no,bi,di,hi,qa,pi,os,uh,wm,an,me,mo,na,la,st,er,sc,ne,mn,mi,am,ex,pt,io,be,fm,ta,tb,ni,mr,pa,he,lr,sq,ye".split(",")));
        List<List<String>> ret = findLadders("hot", "dog", list);
        System.out.println("[" + ret + "]");
    }


    public static List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> ret = new ArrayList<>();
        if (!wordList.contains(endWord)) {
            return ret;
        }

        wordList.add(beginWord);
        int length = wordList.size();
        Map<String, Set<String>> data = new HashMap<>(length);
        Set<String> endSet = new HashSet<>(length);
        endSet.add(endWord);
        BFS(data, beginWord, endSet, wordList);

        ArrayList<String> data1 = new ArrayList<>(2 * length);
        data1.add(beginWord);
        int size = DFS(beginWord, endWord, data, ret, length, data1);
        for (int i = ret.size() - 1; i >= 0; i--) {
            List<String> list = ret.get(i);
            if (list.size() > size) {
                ret.remove(i);
            }
        }
        return ret;
    }

    public static void BFS(Map<String, Set<String>> data, String beginWord, Set<String> endSet, List<String> wordList) {
        Set<String> nextSet = new HashSet<>(wordList.size());
        boolean flag = false;
        wordList.removeAll(endSet);
        for (Iterator<String> iter = endSet.iterator(); iter.hasNext(); ) {
            String endWord = iter.next();

            for (String str : wordList) {
                if (checkDifferent(endWord, str)) {
                    if (beginWord.equals(str)) {
                        flag = true;
                    }
                    Set<String> set = data.computeIfAbsent(str, k -> new HashSet<>(wordList.size()));
                    set.add(endWord);
                    nextSet.add(str);
                }
            }
        }
        if (flag || wordList.size() == 0 || nextSet.size() == 0) {
            return;
        }
        BFS(data, beginWord, nextSet, wordList);
    }

    public static int DFS(String beginWord, String endWord, Map<String, Set<String>> map, List<List<String>> ret, int size, List<String> data) {
        if (beginWord.equals(endWord)) {
            ret.add(new ArrayList<>(data));
            return data.size();
        }
        Set<String> list = map.remove(beginWord);
        if (null == list) {
            return size;
        }
        for (String next : list) {
            data.add(next);
            size = Math.min(size, DFS(next, endWord, map, ret, size, data));
            data.remove(data.size() - 1);
        }
        map.put(beginWord, list);
        return size;
    }

    public static boolean checkDifferent(String ori, String dest) {
        int diff = 0;
        for (int i = ori.length() - 1; i >= 0; i--) {
            if (ori.charAt(i) != dest.charAt(i)) {
                diff++;
            }
        }
        if (diff == 1) {
            return true;
        }
        return false;
    }

}
